package com.zm.exercise.day03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author:Domen
 * @Date:2024/7/12 9:59
 */

public class ComeOn {


    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{3,1,3,4,2}));
    }

    // 寻找重复数 目标时间复杂度O(n) 目前时间复杂度O（n^2)
    public static int findDuplicate(int[] nums) {
//        int n = nums.length;
//        int target = -1;
//
//        for(int i = 0; i< n; i++){
//            for(int j = i+1; j < n-1; j++){
//                if(nums[i] == nums[j]){
//                    target = nums[i];
//                }
//            }
//        }
//        return target;

        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }


    //三数之和 双指针解法
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int len = nums.length;
        //定义最外层循环，即固定最左侧的值,枚举a
        for(int first = 0; first < len; first++){
            //需要和上次枚举的值不同
            if(first> 0 && nums[first] == nums[first-1]){
                continue;
            }

            //取末尾的值为最右侧的数，即c的值
            int third = len -1;
            //定义目标值
            int target = -nums[first];

            //枚举b
            for (int second = first+1; second < len; second++) {
                //需要和上次枚举的值不同
                if (second > first + 1 && nums[second] == nums[second-1]) {
                    continue;
                }
                //b 在 c 的左边
                while (second < third && nums[second] + nums[third] == target){
                    third--;
                }

                if(nums[second] + nums[third] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    lists.add(list);
                }
            }
        }

        return lists;

    }

}
